package org.example.myleet.p741;

public class Solution {

    //两个方向，向右、向下
    private static final int[][] DIRECTIONS = new int[][]{{0, 1}, {1, 0}};

    private static final int CHERRY = 1;
    private static final int BLOCK = -1;

    //记忆化搜索
    private Integer[][][][] memo;

    private int N;

    private int[][] grid;

    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        N = grid.length;
        //x1,y1,x2,y2
        memo = new Integer[N][N][N][N];
        int res = dfs(0, 0, 0, 0);
        return Math.max(0, res);
    }

    private int dfs(int x1, int y1, int x2, int y2) {
        if (x1 == N - 1 && y1 == x1) {
            return grid[N - 1][N - 1];
        }
        if (memo[x1][y1][x2][y2] != null) {
            //记忆化
            return memo[x1][y1][x2][y2];
        }
        //cur-走这一回合获得的樱桃
        int res = Integer.MIN_VALUE, cur = 0;
        if (x1 == x2 && y1 == y2) {
            cur = grid[x1][y1];
        } else {
            cur = grid[x1][y1] + grid[x2][y2];
        }
        for (int[] direction1 : DIRECTIONS) {
            //尝试A的向右或向下
            int nextX1 = direction1[0] + x1;
            int nextY1 = direction1[1] + y1;
            if (nextX1 < N && nextY1 < N && grid[nextX1][nextY1] != BLOCK) {
                for (int[] direction2 : DIRECTIONS) {
                    //尝试B的向右或向下
                    int nextX2 = direction2[0] + x2;
                    int nextY2 = direction2[1] + y2;
                    if (nextX2 < N && nextY2 < N && grid[nextX2][nextY2] != BLOCK) {
                        //通过DFS继续查找下一回合
                        res = Math.max(res, cur + dfs(nextX1, nextY1, nextX2, nextY2));
                    }
                }
            }
        }
        memo[x1][y1][x2][y2] = res;
        return res;
    }
}
